#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    public:
    //遍历
    bool ans1(TreeNode* p, TreeNode* q){
        vector<int> val1;
        vector<int> val2;
        myfrontTraverse(p, val1);
        myfrontTraverse(q, val2);
        int i = 0, len1 = val1.size(), len2 = val2.size();
        if(len1 != len2){
            return false;
        }
        while(i < len1){
            if(val1[i] != val2[i]){
                return false;
            }
            i++;
        }
        return true;
        
    }

    //深度优先
    bool ans2(TreeNode* p, TreeNode* q){
        
        if(p == nullptr && q == nullptr){
            return true;
        }else if(p == nullptr || q == nullptr){
            return false;
        }else if(p->val != q->val){
            return false;
        }else{
            bool ret_l = ans2(p->left, q->left);
            bool ret_r = ans2(p->right, q->right);
            bool ret = ret_l & ret_r;
            return ret;
        }
    }

    //广度优先
    bool ans3(TreeNode* p, TreeNode* q){
        if(p == nullptr && q == nullptr){
            return true;
        }else if(p == nullptr || q == nullptr){
            return false;
        }
        queue<TreeNode*> P, Q;
        P.push(p);
        Q.push(q);
        while(!P.empty() && !Q.empty()){
            TreeNode* temp1 = P.front();
            P.pop();
            TreeNode* temp2 = Q.front();
            Q.pop();
            if(temp1->val != temp2->val){
                return false;
            }
            if((temp1->left == nullptr) ^ (temp2->left == nullptr)){
                return false;
            }
            if((temp1->right == nullptr) ^ (temp2->right == nullptr)){
                return false;
            }
            if(temp1->left){
                P.push(temp1->left);
            }
            if(temp1->right){
                P.push(temp1->right);
            }
            if(temp2->left){
                Q.push(temp1->left);
            }
            if(temp2->right){
                Q.push(temp1->right);
            }
        }
        bool ret = P.empty() & Q.empty();
        return ret;
    }

    void myfrontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            val.push_back(-INT16_MAX);
            return;
        }
        val.push_back(root->val);
        myfrontTraverse(root->left, val);
        myfrontTraverse(root->right, val);
    }


    TreeNode* createTree(vector<int> nums, int index, int len){
        if(nums[index] == '#'){
            return NULL;
        }
        TreeNode* root = new TreeNode(nums[index]);

        if(index * 2 + 1 < len){
            root->left = createTree(nums, index * 2 + 1, len);
        }else{
            root->left = NULL;
        }
        if(index * 2 + 2 < len){
            root->right = createTree(nums, index * 2 + 2, len);
        }else{
            root->right = NULL;
        }
        return root;
    }

    void frontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            val.push_back(-1);
            return;
        }
        val.push_back(root->val);
        frontTraverse(root->left, val);
        frontTraverse(root->right, val);
    }

    void show(vector<int>& val){
        int len = val.size();
        for(int i = 0; i != len-1; i++){
            cout << val[i] << " " << ends;
        }
        cout << val[len-1] << endl;
        val.clear();
    }

};

void test1(){
    Solution s;

    vector<int> p = {1, 2, 3};
    vector<int> q = {1, 2, 3};
    TreeNode* root1 = s.createTree(p, 0, p.size());
    TreeNode* root2 = s.createTree(q, 0, q.size());
    // vector<int> val;
    // s.frontTraverse(root1, val);
    // s.show(val); val.clear();
    // s.frontTraverse(root2, val);
    // s.show(val); val.clear();
    // bool ret = s.ans1(root1, root2);
    // bool ret = s.ans2(root1, root2);
    bool ret = s.ans3(root1, root2);
    cout << ret << endl;
    
}

void test2(){
    Solution s;

    vector<int> p = {1, 2};
    vector<int> q = {1, '#', 2};
    TreeNode* root1 = s.createTree(p, 0, p.size());
    TreeNode* root2 = s.createTree(q, 0, q.size());
    // vector<int> val;
    // s.frontTraverse(root1, val);
    // s.show(val); val.clear();
    // s.frontTraverse(root2, val);
    // s.show(val); val.clear();
    // bool ret = s.ans1(root1, root2);
    // bool ret = s.ans2(root1, root2);
    bool ret = s.ans3(root1, root2);
    cout << ret << endl;
    
}


int main(void){
    test1();
    test2();

    return 0;
}